\section{Rede de Boltzmann Discretizada}

\subsection{Introdu\c{c}\~{a}o}

Ao se tentar solucionar um problema mal colocado utilizando-se redes de
Boltzmann, duas propostas foram levantadas. A primeira est\'{a} relacionada
com a utiliza\c{c}\~{a}o da rede de Boltzmann tradicional, onde grupos de
neur\^{o}nios passem a representar uma determinada vari\'{a}vel, neste caso
discretizada. Esta abordagem se situa muito pr\'{o}xima da solu\c{c}\~{a}o
por algoritmos gen\'{e}ticos \footnote{Para uma refer\^{e}ncia introdut\'{o}ria sobre 
algoritmos gen\'{e}ticos ver \cite{TANG9601}. }
mas com o inconveniente de n\~{a}o apresentar
mecanismos como {\em crossover}, muta\c{c}\~{a}o e cruzamento e, desta forma,
realizando uma busca estatisticamente bem menos abrangente.

Outra possibilidade seria implementar algumas mudan\c{c}as na rede original
de forma que os nodos deixassem de ser bin\'{a}rios e passassem a
representar valores reais. Este modelo, por n\~{a}o necessitar de uma
discretiza\c{c}\~{a}o direta das vari\'{a}veis, ir\'{a} gerar uma rede com
um n\'{u}mero bem menor de nodos que a proposta anterior (ou mesmo uma
estrutura bem menos complexa que algoritmos gen\'{e}ticos). 
A discretiza\c{c}\~{a}o ir\'{a} ocorrer agora nos passos que os valores dos nodos podem dar,
uma vez que eles n\~{a}o possuem um varia\c{c}\~{a}o cont\'{\i}nua.

Este modelo, de agora em diante denominado de rede de Boltzmann Discretizada
(RBD), \'{e} uma contribui\c{c}\~{a}o deste trabalho e ainda est\'{a} em uma fase inicial de 
desenvolvimento. Nas se\c{c}\~{o}es seguintes a RBD ser\'{a} explicada com mais detalhes, 
mostrando suas similaridades e diferen\c{c}as com o modelo cl\'{a}ssico de Bolztmann.  
Grande parte das discuss\~{o}es colocadas relacionadas ao tamanho do
passo, converg\^{e}ncia e espa\c{c}o de busca tamb\'{e}m podem ser vistas em 
um contexto de {\em Simulated Annealing}, no trabalho de Vanderbilt e Louie 
\cite{VANDERBILT8401}. Neste artigo os autores prop\~{o}em um novo algoritmo
para {\em Simulated Annealing} baseado em vari\'{a}veis cont\'{\i}nuas. Novamente \'{e} 
mostrado que 
este m\'{e}todo apresenta vantagens relacionados \`{a} sua natureza estat\'{\i}stica, 
como a possibilidade de escapar de m\'{\i}nimos locais.

\subsection{Estrutura da rede}

De uma maneira geral, este novo modelo guarda v\'{a}rias semelhan\c{c}as com
a rede cl\'{a}ssica, tais com interconex\~{a}o entre os neur\^{o}nios
e regras para mudan\c{c}a de estado baseada em probabilidades.
As principais diferen\c{c}as est\~{a}o relacionadas ao processo como se
d\'{a} a mudan\c{c}a de estado, refinamento e escalonamento da fun\c{c}\~{a}o de energia.

\begin{description}

\item[Mudan\c{c}as de estado.]

No modelo original, os nodos s\~{a}o bin\'{a}rios. Nesta nova proposta, o
nodo passa a representar um valor real. A grande dificuldade para que isto
se torne efetivo est\'{a} relacionada com as mudan\c{c}as de estado em
determinado nodo. Qual deve ser o novo valor do neur\^{o}nio ap\'{o}s uma
mudan\c{c}a de estado ? Esta quest\~{a}o \'{e} resolvida atrav\'{e}s da introdu\c{c}\~{a}o 
de um passo. Os valores dos nodos ir\~{a}o sofrer mudan\c{c}as de acordo
com um passo escolhido.

\item[Refinamento.]

Para que se consiga precis\~{a}o na solu\c{c}\~{a}o encontrada, \`{a} medida que a
converg\^{e}ncia ocorre, o passo deve ser diminu\'{\i}do. Desta forma, passos
iniciais maiores permitem uma busca bem ampla na superf\'{\i}cie a minimizar.
Depois, com as posteriores diminui\c{c}\~{o}es no passo, esta solu\c{c}\~{a}o vai
sendo refinada e o espa\c{c}o de busca se tornando cada vez menor. Este
processo n\~{a}o existe na rede tradicional. Um paralelo poderia ser feito com
o {\em Simulated Annealing} existente no treinamento da
rede de Boltzmann cl\'{a}ssica. Nesta \'{u}ltima, com a diminui\c{c}\~{a}o da
temperatura durante o treinamento, mudan\c{c}as bruscas na solu\c{c}\~{a}o
encontrada s\~{a}o cada vez menos prov\'{a}veis, ou seja, o espa\c{c}o de busca
tamb\'{e}m \'{e}, de certa forma, diminu\'{\i}do quando se tem mais certeza a
respeito da solu\c{c}\~{a}o.

\item[Escalonamento da fun\c{c}\~{a}o de energia.]

Quando o passo diminui, a varia\c{c}\~{a}o de energia que ele pode provocar na
rede tamb\'{e}m diminui. Estas varia\c{c}\~{o}es de energia muito pequenas ir\~{a}o
gerar probabilidades de mudan\c{c}a sempre em torno de $0,5$, fazendo com que
a rede perca a sua capacidade de decidir e passe a realizar itera\c{c}\~{o}es
puramente aleat\'{o}rias. Isto leva \`{a} necessidade de se escalonar a fun\c{c}\~{a}o 
de energia durante o processo de treinamento, ajustando-a sempre, de
forma que as varia\c{c}\~{o}es de energia estejam sempre dentro de uma faixa
adequada. Este processo n\~{a}o apresenta nenhuma similaridade com o modelo
original. Na realidade, cada diminui\c{c}\~{a}o de passo poderia ser encarada
como o in\'{\i}cio de um novo treinamento e o processo de ajuste da escala
ser considerado como a determina\c{c}\~{a}o de um valor inicial.

\end{description}

\subsection{Treinamento}

Aqui, a analogia com a rede de Boltzmann \'{e} quase total. As diferen\c{c}as 
est\~{a}o em basicamente dois pontos:

\begin{enumerate}
\item  Os neur\^{o}nios s\~{a}o inicializados com valores reais e n\~{a}o somente 
$-1$ ou $+1$.

\item  A varia\c{c}\~{a}o do estado do nodo \'{e} um pouco mais complexa.
Primeiramente \'{e} necess\'{a}rio que exista um passo $p$, cujo sinal \'{e}
sorteado aleatoriamente. Ao valor do nodo \'{e} ent\~{a}o adicionado ou n\~{a}o 
um passo $\pm p$ (isto ir\'{a} depender do processo de decis\~{a}o da rede).
\end{enumerate}

Este novo modelo apresenta algumas peculiaridades. Uma delas est\'{a}
relacionada com o passo, que deve ir diminuindo durante o processo de
treinamento para que a resposta final possua alguma precis\~{a}o. Pode-se
dizer que a diminui\c{c}\~{a}o do passo seria equivalente \`{a} diminui\c{c}\~{a}o 
da temperatura no Simulated Annealing. Grandes passos permitem 
varia\c{c}\~{o}es maiores na
fun\c{c}\~{a}o de energia e, consequentemente, no valor dos nodos. Ao
contr\'{a}rio, passos pequenos deixam a fun\c{c}\~{a}o de energia menos
suscept\'{\i}vel \`{a} mudan\c{c}as bruscas.

Por outro lado, a diminui\c{c}\~{a}o do passo, estritamente necess\'{a}ria
para a precis\~{a}o da solu\c{c}\~{a}o, coloca a varia\c{c}\~{a}o da energia
sempre perto de zero. Com isto, a rede perde a sua capacidade de decidir
pois quando esta varia\c{c}\~{a}o de energia \'{e} avaliada pela fun\c{c}\~{a}o de 
transfer\^{e}ncia (no caso, uma sigm\'{o}ide, representada por $Sigm(\Delta H)$), 
esta estar\'{a} sempre em torno de $0,5$, n\~{a}o sendo
capaz de perceber as pequenas varia\c{c}\~{o}es provocadas pelo passo na fun\c{c}\~{a}o de energia.

Com o objetivo de tornar estas diferen\c{c}as mais percept\'{\i}veis,
torna-se necess\'{a}rio incluir um multiplicador na fun\c{c}\~{a}o de
energia. Este multiplicador dever\'{a} ir aumentado \`{a} medida que o passo
diminui de forma que, a cada novo passo, o sistema parta de
um estado de alta energia para um estado de baixa energia. 
Isto \'{e} similar ao algoritmo de Metropolis, que tamb\'{e}m ir\'{a}
ser executado a cada novo passo.

Ao chegar no estado de energia m\'{\i}nima, 
o passo n\~{a}o possui mais resolu\c{c}\~{a}o suficiente para 
refinar a solu\c{c}\~{a}o e o processo deve ser reiniciando com um novo valor
de passo e multiplicador. Isto acontece at\'{e} que o crit\'{e}rio
de converg\^{e}ncia seja satisfeito.

\subsection{Multiplicador da fun\c{c}\~{a}o de energia}
\label{LAB-PARALELISMO}

A rela\c{c}\~{a}o entre este multiplicador e o passo n\~{a}o \'{e} muito bem
estabelecida, al\'{e}m de ser dependente do problema. Dessa forma,
baseado na fun\c{c}\~{a}o de energia descrita no m\'{e}todo B (Se\c{c}\~{a}o 
\ref{SECMETB}), ser\~{a}o desenvolvidas algumas regras
para esta rela\c{c}\~{a}o. Ser\'{a} tamb\'{e}m adicionado a esta fun\c{c}\~{a}o de energia
um termo de regulariza\c{c}\~{a}o e um multiplicador. Esta fun\c{c}\~{a}o
de energia pode ser ent\~{a}o descrita por:

\begin{equation}
E_1\left[ \mathbf{V}\right] =m\left\| \mathbf{AV}-\mathbf{b}\right\| ^2+\lambda \mathbf{V}^T\mathbf{V}
\end{equation}

Ou, se representada por somat\'{o}rios:

\begin{equation}
E_1\left[ \mathbf{V}\right] =m\sum_{i=1}^n\left( \sum_{j=1}^na_{ij}v_j-b_i\right)
^2+\lambda \sum_{i=1}^nv_i^2
\end{equation}

Supondo que um determinado nodo $k$, sorteado aleatoriamente, sofra uma 
varia\c{c}\~{a}o $\Delta v_k=\pm p$, a fun\c{c}\~{a}o de energia ir\'{a}
apresentar uma modifica\c{c}\~{a}o que pode ser dada por:

\begin{equation}
E_2\left[ \mathbf{V}\right] =m\sum_{i=1}^n\left(
\sum_{j=1}^na_{ij}v_j-b_i+a_{ik}\Delta v_k\right) ^2+\lambda
\sum_{i=1}^nv_i^2+\lambda \Delta v_k^2+2\lambda v_k\Delta v_k
\end{equation}

A diferen\c{c}a de energia encontrada ap\'{o}s a varia\c{c}\~{a}o est\'{a} calculada 
a seguir.

\[
\Delta E\left[ \mathbf{V}\right] =E_2\left[ \mathbf{V}\right] -E_1\left[ \mathbf{V}\right] 
\]


\begin{eqnarray*}
\Delta E\left[ \mathbf{V}\right] &=&m\sum_{i=1}^n\left(
\sum_{j=1}^na_{ij}v_j-b_i+a_{ik}\Delta v_k\right) ^2+\lambda
\sum_{i=1}^nv_i^2+\lambda \Delta v_k^2+2\lambda v_k\Delta
v_k - \\ 
&& - m\sum_{i=1}^n\left( \sum_{j=1}^na_{ij}v_j-b_i\right) ^2-\lambda
\sum_{i=1}^nv_i^2 
\end{eqnarray*}


\begin{eqnarray*}
\Delta E\left[ \mathbf{V}\right] &=&m\sum_{i=1}^n\left(
\sum_{j=1}^na_{ij}v_j-b_i\right) ^2+m\sum_{i=1}^n\left(
\sum_{j=1}^na_{ik}\Delta v_k\right) ^2 + \\
&& + 2m\sum_{i=1}^n\left(
\sum_{j=1}^na_{ij}v_j-b_i\right) \left( a_{ik}\Delta v_k\right) - \\
&& - m\sum_{i=1}^n\left( \sum_{j=1}^na_{ij}v_j-b_i\right) ^2+\lambda \Delta
v_k^2+2\lambda v_k\Delta v_k
\end{eqnarray*}

\begin{equation}
\Delta E\left[ \mathbf{V}\right] =m\sum_{i=1}^n\left( \sum_{j=1}^na_{ik}\Delta
v_k\right) ^2+2m\sum_{i=1}^n\left( a_{ik}\Delta
v_k\sum_{j=1}^na_{ij}v_j-b_i\right) +\lambda \Delta v_k^2+2\lambda v_k\Delta
v_k
\end{equation}

Fazendo-se $\mathbf{E}=\mathbf{AV}-\mathbf{b}$ e representando-se a 
\textit{k-\'{e}sima} coluna de $\mathbf{A}$ como $\mathbf{A}_{:k}$, tem-se:

\[
\Delta E\left[ \mathbf{V}\right] =m\Delta v_k^2\mathbf{A}_{:k}^T\mathbf{A}_{:k}+2m\Delta
v_k\mathbf{A}_{:k}^T\mathbf{E}+\lambda \Delta v_k^2+2\lambda v_k\Delta v_k 
\]

\begin{equation}
\Delta E\left[ \mathbf{V}\right] =m\Delta v_k^2\mathbf{A}_{:k}^T\left( \mathbf{A}_{:k}+2\mathbf{E}{\Delta
v_k}\right) +\lambda \Delta v_k^2\left( 1+2\frac{v_k}{\Delta v_k}\right)
\label{EQ-DELTA-ENG}
\end{equation}

A Equa\c{c}\~{a}o \ref{EQ-DELTA-ENG} mostra claramente como a varia\c{c}\~{a}o 
de energia depende do multiplicador. Diminui\c{c}\~{o}es do passo
devem ser seguidas necessariamente de ajustes do multiplicador, de forma que
se tenha uma varia\c{c}\~{a}o de energia adequada para o treinamento, como ser\'{a}
visto mais adiante.
Outro resultado bastante interessante \'{e}
a capacidade de realizar uma busca local uma vez que a varia\c{c}\~{a}o de energia
depende exclusivamente do nodo em que o passo est\'{a} sendo realizado. 
Um algoritmo que realize uma busca paralela poderia tirar
proveito disto, executando concorrentemente a minimiza\c{c}\~{a}o de cada
nodo.

\begin{figure}[!]
\begin{center}
\includegraphics[width=12cm,height=6cm,angle=0]{pss.ps}
\end{center}
\caption{Aspectos da RBD: (a) processo de decis\~{a}o da rede e (b) m\'{a}xima precis\~{a}o para o passo}
\label{FIGPASSO}
\end{figure}

Para iniciar a procura por um novo multiplicador, 
o primeiro problema \'{e} definir quando o passo $p$ come\c{c}a a n\~{a}o
permitir mais nenhuma melhoria na resposta, ou seja, 
definir um crit\'{e}rio para diminui\c{c}\~{a}o do passo. Observando-se a
Figura \ref{FIGPASSO}b n\~{a}o \'{e} dif\'{\i}cil concluir que, ap\'{o}s um n\'{u}mero de itera\c{c}\~{o}es 
suficiente para a converg\^{e}ncia , 
cada coordenada de $\mathbf{b}$ dever\'{a} estar, no pior caso, a uma
dist\^{a}ncia $\pm p/2$ de $\mathbf{AV}$. Com isto, \'{e} poss\'{\i}vel saber quando
o passo atual j\'{a} alcan\c{c}ou o seu limite. Desta forma, pode-se definir
a seguinte fun\c{c}\~{a}o de erro:

\begin{equation}
Erro_p=\frac{1}{n}\sum_{j=1}^n\left| a_{ij}v_j-b_i\right|
\end{equation}

A vari\'{a}vel $n$ representa a dimens\~{a}o do vetor $\mathbf{V}$. Pode-se verificar
que esta fun\c{c}\~{a}o ir\'{a} tender para um valor limite de $p/2$,
indicando desta forma quando o passo deve ser diminu\'{\i}do. Na
pr\'{a}tica, um crit\'{e}rio um pouco menos r\'{\i}gido pode ser usado, uma
vez que o tempo gasto para que este crit\'{e}rio te\'{o}rico seja atendido
\'{e} relativamente maior.

Com a diminui\c{c}\~{a}o do passo, a varia\c{c}\~{a}o de energia provocada
pelo novo passo ser\'{a} bem menor em rela\c{c}\~{a}o ao anterior. Neste
ponto, o multiplicador deve ser ajustado. 
O que se pretende \'{e} que o
multiplicador ofere\c{c}a uma varia\c{c}\~{a}o de energia dentro de uma faixa
aceit\'{a}vel, permitindo assim uma busca estatisticamente mais eficiente.

Ao se analisar conjuntamente a varia\c{c}\~{a}o de energia e o histograma da
probabilidade de mudan\c{c}a de estado ($Sigm(\Delta E)$) depois de
v\'{a}rias itera\c{c}\~{o}es, pode-se ter uma id\'{e}ia de como determinar
um valor \'{o}timo para este multiplicador.

Tentando-se apresentar as tr\^{e}s situa\c{c}\~{o}es t\'{\i}picas
encontradas durante o processo de treinamento, foram levantados
tr\^{e}s histogramas de $Sigm(\Delta E)$ ap\'{o}s 8000 itera\c{c}\~{o}es.
S\~{a}o utilizados valores diferentes de $m$ mas a mesma parametriza\c{c}\~{a}o 
inicial para a rede.

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=16cm,angle=-90]{stdgeral.ps}
\end{center}
\caption{Influ\^{e}ncia do desvio padr\~{a}o}
\label{FIGSTDGERAL}
\end{figure}

Na Figura \ref{FIGSTDGERAL}a pode ser visto um caso onde o valor do multiplicador \'{e}
muito pequeno, ou seja, a varia\c{c}\~{a}o de energia est\'{a} sempre muito
pr\'{o}xima de zero. Quando isto acontece, a rede se encontra em um estado
que \'{e} equivalente ao estado inicial de uma rede de Boltzmann
bin\'{a}ria, ou seja, com alta temperatura. Nesta situa\c{c}\~{a}o, a rede
troca frequentemente o valor dos nodos devido \`{a} sua grande energia.
Isto pode ser interessante para permitir inicialmente uma
procura mais abrangente no espa\c{c}o de busca mas ao se utilizar
este valor do multiplicador durante toda a fase do treinamento o que
se nota \'{e} uma inefici\^{e}ncia do algoritmo. 

A Figura \ref{FIGSTDGERAL}c mostra outro caso extremo, mas agora com um valor de
multiplicador muito grande. A consequ\^{e}ncia disto \'{e} uma alta
frequ\^{e}ncia em torno dos valores 0 e 1. Neste caso, a rede perde a sua
caracter\'{\i}stica estoc\'{a}stica, sendo que varia\c{c}\~{o}es negativas
de energia levam \`{a} mudan\c{c}as de estado e varia\c{c}\~{o}es positivas
de energia n\~{a}o. Consequentemente, fica clara a inabilidade da rede para
escapar de m\'{\i}nimos locais e de varrer corretamente o espa\c{c}o de
busca.

Finalmente, a Figure \ref{FIGSTDGERAL}b apresentam uma rede equilibrada, onde as
frequ\^{e}ncias de $Sigm(\Delta E)$ est\~{a}o variando em torno de 0,5
simetricamente, evidenciando casos onde a rede tem uma leve certeza sobre a
aceita\c{c}\~{a}o/rejei\c{c}\~{a}o do novo estado. Al\'{e}m disso, o
histograma mostra claramente situa\c{c}\~{o}es onde a varia\c{c}\~{a}o de
energia \'{e} grande o suficiente para que a rede decida, com seguran\c{c}a
sobre a aceita\c{c}\~{a}o/rejei\c{c}\~{a}o. As frequ\^{e}ncias em torno de 0
e 1 representam estes casos.

Na pr\'{a}tica, descobriu-se que um valor razo\'{a}vel para o desvio
padr\~{a}o de $Sigm(\Delta E)$ est\'{a} situado entre 0,30 e 0,35,
produzindo histogramas como o da Figura \ref{FIGSTDGERAL}b.

\subsection{Algoritmo de treinamento}

Para o treinamento da RBD foi desenvolvido um algoritmo capaz de realizar
automaticamente as diminui\c{c}\~{o}es de passo e ajustes do multiplicador,
enquanto a busca do m\'{\i}nimo \'{e} feita. Este algoritmo possui uma
esp\'{e}cie de supervisor que, depois de um certo n\'{u}mero de itera\c{c}\~{o}es, 
reavalia estatisticamente a rede e decide sobre os novos valores do
passo e do multiplicador. Al\'{e}m disso, este supervisor \'{e} capaz de
rejeitar o \'{u}ltimo grupo de itera\c{c}\~{o}es caso elas n\~{a}o tenham
sido realizadas dentro de uma faixa aceit\'{a}vel para o desvio padr\~{a}o
de $Sigm(\Delta E)$. Isto \'{e} necess\'{a}rio porque se percebeu que a
rede, ao realizar itera\c{c}\~{o}es com valores inadequados para o desvio
padr\~{a}o, acaba por distanciar-se da solu\c{c}\~{a}o, tornando o processo
da converg\^{e}ncia lento e impreciso.


